/*
 * @lc app=leetcode id=160 lang=cpp
 *
 * [160] Intersection of Two Linked Lists
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) {
            return NULL;
        }

        ListNode *nodeA = headA;
        ListNode *nodeB = headB;
        int la = getLen(nodeA);
        int lb = getLen(nodeB);
        int l;

        nodeA = headA;
        nodeB = headB;
        if (la > lb) {
            l = la-lb;
            while (l-- > 0) {
                nodeA = nodeA->next;
            }
        } else {
            l = lb-la;
            while (l-- > 0) {
                nodeB = nodeB->next;
            }
        }

        while (nodeA && nodeB && nodeA != nodeB) {
            nodeA = nodeA->next;
            nodeB = nodeB->next;
        }

        if (nodeA && nodeB) {
            return nodeA;
        }

        return NULL;
    }

    int getLen(ListNode *node) {
        int l = 0;
        while (node) {
            l++;
            node = node->next;
        }
        return l;
    }
};

